package com.mystudy.leetcode.problem.tree.p_538;

import com.mystudy.leetcode.base.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @program: infoalgorithm
 * @description: 把二叉搜索树转换成累加树
 * @author: zhouzhilong
 * @create: 2019-07-24 17:46
 **/
public class Solution {
    /**
     * 土鳖做法
     * @param root
     * @return
     */
    public TreeNode convertBST(TreeNode root) {
        //先中序遍历，得到一个顺序的列表
        List<Integer> result = new ArrayList<>();
        inOrder(root,result);

        //然后重新遍历并赋值
        preOrderAndReset(root,result);
        return root;
    }

    private void inOrder(TreeNode node, List<Integer> result) {
        if(node == null){
            return;
        }
        inOrder(node.left,result);
        result.add(node.val);
        inOrder(node.right,result);
    }

    private void preOrderAndReset(TreeNode node,List<Integer> result){
        if(node == null){
            return;
        }

        int index = result.indexOf(node.val);
        for (int i = index+1; i < result.size(); i++) {
                node.val = node.val+result.get(i);
        }

        preOrderAndReset(node.left,result);
        preOrderAndReset(node.right,result);
    }


}
